package com.mamingchao.basic.swardToOffer.LRU;

import com.mamingchao.basic.chain.ChainNode;

import java.util.HashMap;
import java.util.Objects;

/**
 * 双向链表tail为 时间最近使用的节点；
 * head 是时间最久没使用的节点
 */
public class LRUCache {

    // 双向链表头结点
    private ChainNode head;
    // 双向链表尾结点
    private ChainNode tail;
    //缓存容量
    private int capacity;

    //节点数量计数器
    private int counter;

    //Hash 缓存结构
    private HashMap<String, ChainNode> map = new HashMap<>();

    public LRUCache(){
        this(10);
    }

    public LRUCache(int capacity){
        this.capacity = capacity;
    }

    public void putLast(ChainNode chainNode) {

        // 如果链表大小已经是满的，则需要剔除一个；从head 开始踢
        if (counter == capacity) {
            map.put(chainNode.getValue(), chainNode);
            map.remove(this.head.getValue());
            removeHead();
            this.appendToTail(chainNode);
        } else {
            // 如果链表大小 尚未满，则直接拼接到双向链表的tail上，同时map 也增加上
            map.put(chainNode.getValue(), chainNode);

            // 再把 chainNode 拼到 链表的最后
            this.appendToTail(chainNode);
            counter ++;
        }
    }

    /**
     * 获取节点
     * @param key
     * @return
     */
    public ChainNode get(String key) {
        if (map.containsKey(key)){
            ChainNode cur =  map.get(key);

            // 如果读取的就是双向链表的尾巴，直接 从hash 结构中返回即可；链表不调整
            // 如果读取的不是双向链表的尾巴，这需要调整链表中元素的相互顺序
            if (!Objects.equals(cur, this.tail)) {
                //先把目标节点从链表中摘出来
                this.removeNodeInChain(cur);
                // 再把 cur 拼到 链表的最后
                this.appendToTail(cur);
            }
            return  cur;
        }
        return null;
    }

    private void removeNodeInChain(ChainNode chainNode){
        chainNode.getNext().setPre(chainNode.getPre());

        // 如果cur是 head节点，他没有pre指针
        // 如果chainNode是链表中间节点
        if (Objects.nonNull(chainNode.getPre())) {
            chainNode.getPre().setNext(chainNode.getNext());
            chainNode.setPre(null);
        } else {
            // 如果 chainNode 是头结点，头结点移除，把头结点指到nextNode上
            this.head = chainNode.getNext();
        }

        chainNode.setNext(null);
        map.remove(chainNode.getValue());
    }


    public void clear() {
        while (this.head != null) {
            ChainNode cur = this.head;
            this.head = this.head.getNext();
            cur = null;
        }
        map.clear();
        this.counter = 0;
    }


    // 再把 cur 拼到 链表的最后
    private void appendToTail(ChainNode chainNode){
        // 当 this.tail 为null的时候，表示 是空队列
        if (Objects.isNull(this.tail)) {
            this.head = chainNode;
            this.tail = chainNode;
        } else {
            chainNode.setPre(this.tail);
            chainNode.setNext(null);
            this.tail.setNext(chainNode);
            this.tail = chainNode;
        }
        this.map.put(chainNode.getValue(), chainNode);
    }


    /**
     * 移除 双向链表头部节点
     */
    private void removeHead(){
        ChainNode next = this.head.getNext();

        next.setPre(null);
        this.head.setNext(null);
        this.head = next;
    }


    public static void main(String[] args) {
        ChainNode one = new ChainNode("1");
        ChainNode two = new ChainNode("2");
        ChainNode three = new ChainNode("3");
        ChainNode four = new ChainNode("4");
        ChainNode five = new ChainNode("5");

        LRUCache lruCache = new LRUCache(3);
        lruCache.putLast(one);
        lruCache.putLast(two);
        lruCache.putLast(three);

        ChainNode starter = lruCache.head;
        while (starter != null) {
            System.out.println(starter.getValue());
            starter = starter.getNext();
        }

        lruCache.get("2");
        System.out.println("----------------------");
        starter = lruCache.head;
        while (starter != null) {
            System.out.println(starter.getValue());
            starter = starter.getNext();
        }


        lruCache.putLast(four);

        System.out.println("----------------------");
        starter = lruCache.head;
        while (starter != null) {
            System.out.println(starter.getValue());
            starter = starter.getNext();
        }
    }
}
